package 链表;
import java.util.*;
//https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6
public class Solution3 {//思路：遍历它们，把值放到一个数组，排序，再创节点连起来
    public ListNode mergeKLists1 (ArrayList<ListNode> lists) {
        //用辅助头节点：
        ListNode assHead = new ListNode(0);
        ListNode tail = assHead;

        List<Integer> arrayList = new ArrayList<>();
        for (ListNode cur : lists) {
            while (cur != null) {
                arrayList.add(cur.val);
                cur = cur.next;
            }
        }
        //排序：<Integer>的就会以Integer的大小来比较
        Collections.sort(arrayList);

        for (Integer integer : arrayList) {
            tail.next = new ListNode(integer);
            tail = tail.next;
        }
        return assHead.next;
    }
    public static ListNode mergeKLists (ArrayList<ListNode> lists) {//思路：优先级队列来做
        PriorityQueue<ListNode> priorityQueue = new PriorityQueue<>((a,b) -> a.val - b.val);
        ListNode dummp = new ListNode(0);
        ListNode current = dummp;
        for (ListNode listNode: lists) {
            if(listNode != null) {//数组里的头节点可能有空的，不能offer空的
                priorityQueue.offer(listNode);//节点没有定义大小比较规则，<LinsNode>，ListNode没有定义大小比较规则
            }
        }
        while (!priorityQueue.isEmpty()) {
            current.next = priorityQueue.poll();
            if(current.next.next != null) {
                priorityQueue.offer(current.next.next);
            }
            current = current.next;
        }
        return dummp.next;
    }

    public static void main(String[] args) {
        ArrayList<ListNode> arrayList = new ArrayList<>();
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        node1.next = node2;
        node2.next = node3;
        arrayList.add(node1);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        ListNode node6 = new ListNode(6);
        ListNode node7 = new ListNode(7);
        node4.next = node5;
        node5.next = node6;
        node6.next = node7;
        arrayList.add(node4);
        mergeKLists(arrayList);
        System.out.println("=======");
    }
}
